//Copyright (c) Microsoft Corporation.  All rights reserved.

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace Eas.WebCrawler.Common.Collections
{
    /// <summary>A binary heap that guaruntees that O(Log) access to the highest priority element and O(Log) insert.</summary>
    /// <typeparam name="T">The type of object contained in the heap.</typeparam>
    /// <remarks>Items are considered to have a higher priority if they have a lower sort order.</remarks>
    public sealed class BinaryHeap<T> : IEnumerable<T>, ICollection, IEnumerable, ICollection<T>
    {
        IComparer<T> _comparer = null;
        List<T> _data;
        /// <summary>Constructs a binary heap.</summary>
        public BinaryHeap()
        {
            _data = new List<T>();
            _data.Add(default(T));
        }

        /// <summary>Creates a binary heap from the initial capacity of the heeap.</summary>
        /// <param name="capacity">The initial capacity of the heap, not the count.</param>
        /// <remarks>capcity is how much space is initally allocated in the heap to store items, not the count of actually stored items.</remarks>
        public BinaryHeap(int capacity)
        {
            _data.Add(default(T));
            _data = new List<T>(capacity);
        }

        /// <summary>Creates a binary heap from an initial collection of items used to populate the heap.</summary>
        /// <param name="collection">The initial collection of items used to populate the heap.</param>
        public BinaryHeap(IEnumerable<T> collection) : this() 
        {
            AddRange(collection);
        }

        /// <summary>Creates a heap from a comparer used to determine the priority of items in the heap.</summary>
        /// <param name="comparer">comparer used to determine the priority of items in the heap.</param>
        /// <remarks>Items are considered to have higher priority if the have a lower sort order.</remarks>
        public BinaryHeap(IComparer<T> comparer) : this()
        {
            _comparer = comparer;
        }

        /// <summary>Constructs a heap from  an initial capacity and a comparer used to determine priority.</summary>
        /// <param name="capacity">The initial capacity of the heap, not the count.</param>
        /// <param name="comparer">comparer used to determine the priority of items in the heap.</param>
        /// <remarks>capcity is how much space is initally allocated in the heap to store items, not the count of actually stored items.</remarks>
        public BinaryHeap(int capacity, IComparer<T> comparer)
            : this(capacity)
        {
            _comparer = comparer;
        }

        /// <summary>Constructs a binary heap from an initial collection of items and a comparer used to determine the priority of items.</summary>
        /// <param name="collection">The initial collection of items used to populate the heap.</param>
        /// <param name="comparer">comparer used to determine the priority of items in the heap.</param>
        public BinaryHeap(IEnumerable<T> collection, IComparer<T> comparer)
            : this(comparer)
        {
            AddRange(collection);
        }

        /// <summary>Removes all itesm from the collection.</summary>
        public void Clear() {
            _data.Clear();
            _data.Add(default(T));
        }

        /// <summary>Returns the highest priority item from the heap without removing the heap.</summary>
        /// <returns>The highest priority item in the heap.</returns>
        public T Peek()
        {
            if (Count == 0)
                throw new InvalidOperationException("Count is empty");
            //remember: _data[0] is empty.
            return _data[1];
        }

        /// <summary>Removes the highest priority item from the heap and returns it.</summary>
        /// <returns>The highest priority item in the heap.</returns>
        public T Pop() 
        {
            if (Count == 0)
                throw new InvalidOperationException("Count is empty");
            //remember: _data[0] is empty.
            T result = _data[1];
            _data[1] = _data[_data.Count - 1];
            _data.RemoveAt(_data.Count - 1);
            if(_data.Count>1)
                PercolateDown(1);
            return result;
        }

        /// <summary>The comparer used to determine the priority of items in the heap.</summary>
        public IComparer<T> Comparer
        {
            get { return _comparer; }
            set { _comparer = value; }
        }
        
        /// <summary>Enumerates over  all the items in the heap in priority order, removing each one from the heap as it does so.</summary>
        /// <returns>An enumeration of all the items in the heap returned in priority order.</returns>
        public IEnumerable<T> PopAllItemsInOrder()
        {
            while (_data.Count > 1)
            {
                yield return Pop();
            }
        }

        /// <summary>Adds an item to the heap.</summary>
        /// <param name="item">The item to add</param>
        public void Add(T item) 
        {
            _data.Add(item);
            PercolateUp(_data.Count - 1, _data[_data.Count-1]);
        }

        /// <summary>Adds a collection of items to the heap.</summary>
        /// <param name="collection">An enumeration of all the items to add</param>
        public void AddRange(IEnumerable<T> collection)
        {
            _data.AddRange(collection);
            FixHeap();
        }

        private void FixHeap() {
            for (int i = _data.Count /2; i > 0; i--)
            {
                PercolateDownWithoutValidate(i);
            }
        }

        private void PercolateUp(int index, T value) 
        {
            int parent = index / 2;
            while (index > 1 && !Compare(_data[parent], value))
            {
                _data[index] = _data[parent];
                index = parent;
                parent = parent / 2;
            }
            _data[index] = value;

        }

        private bool Compare(T first, T second)
        {
            if (_comparer != null)
                return _comparer.Compare(first, second) < 1;
            IComparable<T> firstAsIComparableOfT = first as IComparable<T>;
            if (firstAsIComparableOfT != null)
                return (firstAsIComparableOfT).CompareTo(second) < 1;
            IComparable firstAsIComparable = first as IComparable;
            if (firstAsIComparable!=null)
                return (firstAsIComparable).CompareTo(second) < 1;
            throw new InvalidOperationException("Can not use a binary heap with items that are not comparable unless you explicitly specify a comparer.  Type '" + typeof(T).FullName + "' does not implement IComparable.");
        }

        private void PercolateDown(int holeIndex)
        {
            PercolateDownWithoutValidate(holeIndex);
        }

        private void PercolateDownWithoutValidate(int holeIndex)
        {
            T holeValue = _data[holeIndex];
            int selectedChildIndex = holeIndex * 2;
            while (selectedChildIndex < _data.Count)
            {
                T selectedChildValue = _data[selectedChildIndex];

                if (selectedChildIndex + 1 < _data.Count && !Compare(selectedChildValue, _data[selectedChildIndex + 1]))
                {
                    ++selectedChildIndex;
                    selectedChildValue = _data[selectedChildIndex];
                }
                if (Compare(holeValue, selectedChildValue))
                    break;
                else
                {
                    _data[holeIndex] = selectedChildValue;

                    holeIndex = selectedChildIndex;
                    selectedChildIndex = holeIndex * 2;
                }
            }
            _data[holeIndex] = holeValue;
        }

        #region ICollection Members

        /// <summary>Copies the items in the heap into an array.  Items are not copied in priority order.</summary>
        /// <param name="array">The array into which items should be copied.</param>
        /// <param name="index">The indes at which to start copying items into the array.</param>
        public void CopyTo(Array array, int index) {
            T[] typedArray = (T[])array;
            _data.CopyTo(typedArray, index);
        }

        /// <summary>The number of items in the heap.</summary>
        public int Count {
            get { return _data.Count - 1; }
        }

        /// <summary>Whether or not this collection is synchronized.</summary>
        public bool IsSynchronized {
            get { return false; }
        }

        /// <summary>A root object which can be used for locking when using this collection in a multithreaded environment.</summary>
        public object SyncRoot {
            get { return this; }
        }

        #endregion

        #region IEnumerable Members

        /// <summary>Returns an enumeration of all items in the heap but not in priority order.</summary>
        /// <returns>an enumeration of all items in the heap.</returns>
        IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            return _data.GetEnumerator();
        }

        #endregion

        #region IEnumerable<T> Members
        /// <summary>Returns an enumeration of all items in the heap but not in priority order.</summary>
        /// <returns>an enumeration of all items in the heap.</returns>
        IEnumerator<T> IEnumerable<T>.GetEnumerator() {
            return _data.GetEnumerator();
        }

        #endregion

        #region ICollection<T> Members

        /// <summary>Checks whether an item is contained in the heap.</summary>
        /// <param name="item">The item to look for</param>
        /// <returns><code>true</code> if the item is contained in the heap, otherwise <code>false</code>.</returns>
        public bool Contains(T item) {
            return _data.Contains(item);
        }
        /// <summary>Copies the items in the heap into an array.</summary>
        /// <param name="array">The array into which items should be copied.</param>
        /// <param name="arrayIndex">The place in the array at which copying should begin.</param>
        public void CopyTo(T[] array, int arrayIndex) {
            _data.CopyTo(array, arrayIndex);
        }

        /// <summary>Whether or not this item is read only.</summary>
        public bool IsReadOnly {
            get { return false; }
        }

        /// <summary>Removes an item from the heap.</summary>
        /// <param name="item">The item to remove.</param>
        /// <returns><code>true</code> if the item was found and removed, otherwise <code>false</code>.</returns>
        /// <remarks>This api is much less performant than <see cref="Pop"/> though it allows removal of arbitrary elements.</remarks>
        public bool Remove(T item) {
            bool returnValue = _data.Remove(item);
            if(returnValue)
                this.FixHeap();
            return returnValue;
        }

        #endregion
    }
}
